package LinkedList;

/**
 * 给定两个单链表的头节点headA 和 headB ，请找出并返回两个单链表相交的起始节点。d
 * 如果两个链表没有交点，返回 null 。
 */
public class OfferP23 {

    public static final int NUMBER = 30001;

    /**
     * 法一 ：
     * 由于两条链表的重合节点只可能出现在链表的尾部，
     * 即，想法在于使用栈来存储链表的节点，从两条链表的尾部开始逐个开始比较,直至出现不相同的元素为止
     * @param headA
     * @param headB
     * @return
     */
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//
//        // 若是链表为空的话，即不成立
//        if (headA == null || headB == null){
//            return null;
//        }
//
//        ListNode arrayA[] = new ListNode[NUMBER];
//        ListNode arrayB[] = new ListNode[NUMBER];
//        int Alength = 0, Blength = 0;
////        ListNode dummyA = new ListNode(-1);
////        ListNode dummyB = new ListNode(-2);
////        arrayA[0] = dummyA;
////        arrayB[0] = dummyB;
//        // 记录链表中元素的个数（由于使用数组，作为栈来存储数据，需要知道数组的长度，才能从数组的尾部进行比较）
//        while(headA != null){
//            arrayA[++Alength] = headA;
//            headA = headA.next;
//        }
//        while (headB != null){
//            arrayB[++Blength] = headB;
//            headB = headB.next;
//        }
////        System.out.println(Alength);
////        System.out.println(Blength);
//
//        while(Alength > 0 && Blength > 0){
//            /**
//             *  此处若是两条链表完全相等的话，则不会返回节点；
//              */
//            // 此处的情况，即为两条链表中的值不相等（节点不重合）
//            if(arrayA[Alength] != arrayB[Blength]){
//                return arrayA[Alength + 1];
//            }
//            Alength--;
//            Blength--;
//        }
//        /**
//         * 若是跳出循环的话，即代表已经有链表遍历完成
//         */
//        if(Alength == 0){
//            return arrayA[1];
//        }
//            return arrayB[1];
//    }

    /**
     * 方法二 ：
     * 由于两台链表的长度不统一，即，从头开始遍历时，两条链表到达尾部的时间不一致；
     * 为解决此问题，即我们需要去
     * （1）先获取链表的长度
     * （2）指向长链表先移动长链表若干步，使得长链表的指针与 短链表的指针能够同时到达尾部
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 获取链表的长度
        int lengthA = countLength(headA);
        int lengthB = countLength(headB);
        // 判断A和B链表的长度大小，将长链表的指针先移动若干步，保证长链表和短链表的指针同时到达1链表的尾部
        int steps = Math.abs(lengthA - lengthB);
        // 判断链表的长度，从而指定longer指针指向 A链表还是B链表的头节点,shorter指针指向短链表的头节点（双指针）
        ListNode longer = lengthA > lengthB ? headA : headB;
        ListNode shorter = lengthA > lengthB ? headB : headA;
        for(int i = 0 ;i < steps ; i++){
            longer = longer.next;
        }
        /*int steps = lengthA > lengthB ? lengthA - lengthB : lengthB - lengthA;
        if(lengthA > lengthB){
            for(int i = 0 ;i < steps; i++){
                headA = headA.next;
            }
        }
        else {
            for(int i = 0 ;i < steps; i++){
                headB = headB.next;
            }
        }*/

        // 即，当链表节点不一致时，向后遍历，直至链表
        while(longer != shorter){
            longer = longer.next;
            shorter = shorter.next;
        }
        // 注意 ：若是不存在重合的节点，即head节点指向null，所以不需要额外判断
        return shorter;
    }
    // 获取链表的长度
    private int countLength(ListNode head){
        int length = 0;
        while(head != null){
            length++;
            head = head.next;
        }
        return length;
    }
}
